1. Field of the Invention
The present invention relates to a method for writing and reading a memory, and more particularly, to a method for writing and reading a memory of a block interleaver.
2. Description of the Related Art
Error-correction codes are often used in digital communication systems to correct errors produced during data transmission. Generally speaking, the number of errors an error-correction code can correct for a certain amount of data is limited. For example, a (7, 4) Hamming code can only correct 1 bit of error or detect 2 bits of errors per 7 bits of input data. However, a burst error, or a sequence of errors, often occurs during data transmission such that the number of errors is beyond an error-correction code's capability. Accordingly, most digital communication systems utilize interleaver systems, such as block interleaves, to redistribute the sequence of errors such that those errors are distributed more evenly, and the error-correction code can therefore effectively correct those errors.
FIG. 1 shows the block diagram of a block interleaver. As shown in FIG. 1, the block interleaver 100 comprises a memory 110 and a combinational circuit 120. The size of the memory 110 is Nr rows by Nc columns. The effective size of the memory 110 varies for different transmission requirements. Therefore, it is not necessary for the memory 110 to use all of its capacity during read/write operation. Data is transversally written to the memory 110 and vertically read from the memory 110 such that the data is interleaved. Generally, the memory 110 is realized by registers, and the read and write operation of the memory 110 is controlled by the combinational circuit 120.
FIG. 2 shows the flow chart of a conventional method for writing a memory of a block interleaver, wherein the size of the memory is Nr rows by Nc columns, and the method writing a datum of NBPSC bits transversally into the memory with a start address of the r-th row and the c-th column of the memory. In step 210, a first temporary row with length Nc bits is established, wherein NBPSC entries starting from the c-th entry of the first temporary row are marked as 1, and the other entries of the first temporary row are marked as 0. In step 220, the datum with the length of NBPSC bits is expanded to a second temporary row with length of Nc bits such that the least significant bit of the datum is mapped to the c-th entry of the second temporary row, and the remaining entries are marked as 0. In step 230, the r-th row of the memory is read, and AND operations are executed to each bit of the r-th row of the memory with each bit of the first temporary row to generate a third temporary row. In step 240, OR operations are executed to each bit of the second temporary row with each bit of the third temporary row, and the result is written to the r-th row of the memory.
The realization of the aforementioned writing method incurs significant hardware costs. For example, step 230 requires a multiplexer with Nr inputs terminal to read the r-th row of the memory, and each input datum of the multiplexer is Nc bits in length. Therefore, the multiplexer comprises a majority of the area of the writing circuit of the block interleaver. In addition, in steps 230 and 240, an AND gate and an OR gate with length Nc bits are required respectively such that the area of the writing circuit is further increased.
FIG. 3 shows the flow chart of a conventional method for reading a memory of a block interleaver, wherein the size of the memory is Nr rows by Nc columns, the effective size of the memory is Mr rows by Mc columns, and the method includes reading a datum of NBPSC bits vertically from the memory with a start address of the r-th row and the c-th column of the memory. However, the effective size of the memory might be smaller than the real size of the memory, and the datum to be read might be divided into two columns. Therefore, the reading method determines the corresponding addresses of each bit individually based on several criteria. In step 310, the bit stored in the entry of r-th row and the c-th column of the memory is read as the first bit of the datum. In step 320, the corresponding address of each bit from the second to the NBPSC bit of the datum is determined. In step 330, the bits stored in the entries corresponding to the determined address are read as the second to the NBPSC bit of the datum. The criteria for the determination of the addresses are as follows: to determine the corresponding address of the m-th bit of the datum, wherein 2≦m≦NBPSC, check whether r+m−1 is equal to or smaller than Mr. If r+m−1 is equal to or smaller than Mr, then the bit stored in the entry of the (r+m−1)-th row and the (c+1)-th column of the memory is read as the m-th bit of the datum. If r+m−1 is greater than Mr, then check whether c+1 is equal to or smaller than Mc. If c+1 is equal to or smaller than Mc, then the bit stored in the entry of the (r+m−1−Mr)-th row and the (c+1)-th column of the memory is read as the m-th bit of the datum. If c+1 is greater than Mc, then the bit stored in the entry of the (r+m−1−Mr)-th row and the first column of the memory is read as the m-th bit of the datum.
The realization of the aforementioned reading method incurs significant hardware costs. For example, step 320 requires many addition and subtraction operations and determination criteria for each bit of the datum such that the area of the reading circuit of the block interleaver is significantly increased.
In conclusion, the hardware cost and space required for the memory of a block interleaver are limited and fixed, and the structure of the combinational circuit of the block interleaver is based on the writing and reading method of the block interleaver. Therefore, there is a need to design writing and reading methods for a block interleaver with low complexity to reduce the hardware requirement of the block interleaver.